package com.solution.depthFirstSearch;

import java.util.ArrayList;
import java.util.List;

/*
【解释1】由于结果集根据数组元素求排列（而不是求组合），所以结果集数量=nums.size!（的阶乘）
 */
public class Solution {

    private int[] nums;
    private List<List<Integer>> result;
    private int n;

    public List<List<Integer>> permute(int[] nums) {
        this.n = nums.length;
        this.nums = nums;
        boolean[] visited = new boolean[n];  // 已访问位，默认填充false
        this.result = new ArrayList<>( factorial(n) );  // 见【解释1】
        dfs(visited, new ArrayList<>(n));
        return result;
    }

    private void dfs(boolean[] visited, ArrayList<Integer> tmp) {
        if ( tmp.size() == n ) {
            result.add(new ArrayList<>(tmp));  // 精髓
            return;
        }
        for ( int i = 0 ; i < n ; i++ ) {
            if ( visited[i] == true ) continue;
            visited[i] = true;
            tmp.add(nums[i]);
            dfs(visited, tmp);
            visited[i] = false;
            tmp.remove(tmp.size() - 1);  // 精髓，移除当前不再使用的元素，与上一行visited[i] = false;逻辑同比
        }
    }

    private int factorial(int n) {
        if ( n < 1 )
            return 0;
        if ( n == 1 )
            return 1;
        return n * factorial(n - 1);
    }

}
